|
The constructive cooperative coevolutionary algorithm (also called C3) is an global optimisation algorithm in artificial intelligence based on the multi-start architecture of the greedy randomized adaptive search procedure (GRASP).〔T.A. Feo and M.G.C. Resende (1989) A probabilistic heuristic for a computationally difficult set covering problem. ''Operations Research Letters'', 8:67–71, 1989.〕〔T.A. Feo and M.G.C. Resende (1995) Greedy randomized adaptive search procedures. ''J. of Global Optimization'', 6:109–133, 1995.〕 It incorporates the existing cooperative coevolutionary algorithm (CC).〔M. A. Potter and K. A. D. Jong, A cooperative coevolutionary approach to function optimization, in ''PPSN III: Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature'' London, UK:Springer-Verlag, 1994, pp. 249–257.〕 The considered problem is decomposed into subproblems. These subproblems are optimised separately while exchanging information in order to solve the complete problem. An optimisation algorithm, usually but not necessarily an evolutionary algorithm, is embedded in C3 for optimising those subproblems. The nature of the embedded optimisation algorithm determines whether C3's behaviour is deterministic or stochastic. The C3 optimisation algorithm was originally designed for simulation-based optimisation〔〔 but it can be used for global optimisation problems in general.〔 Its strength over other optimisation algorithms, specifically cooperative coevolution, is that it is better able to handle non-separable optimisation problems.〔〔Glorieux E., Danielsson F., Svensson B., Lennartson B.: Constructive cooperative coevolutionary optimisation for interacting production stations, ''International Journal of Advanced Manufacturing Technology'', 2015.〕 ==Algorithm== As shown in the pseudo code below, an iteration of C3 exists of two phases. In Phase I, the constructive phase, a feasible solution for the entire problem is constructed in a stepwise manner. Considering a different subproblem in each step. After the final step, all subproblems are considered and a solution for the complete problem has been constructed. This constructed solution is then used as initial solution in Phase II, the local improvement phase. The CC algorithm is employed to further optimise the constructed solution. A cycle of Phase II includes optimising the subproblems separately while keeping the parameters of the other subproblems fixed to a central blackboard solution. When this is done for each subproblem, the found solution are combined during a "collaboration" step, and the best one among the produced combinations becomes the blackboard solution for the next cycle. In the next cycle, the same is repeated. Phase II, and thereby the current iteration, are terminated when the search of the CC algorithm stagnates and no significantly better solutions are being found. Then, the next iteration is started. At the start of the next iteration, a new feasible solution is constructed, utilising solutions that were found during the Phase I of the previous iteraton(s). This constructed solution is then used as initial solution in Phase II in the same way as in the first iteration. This is repeated until one of the termination criteria for the optimisation is reached, e.g. maximum number of evaluations. ← ∅ WHILE termination criteria not satisfied DO IF == ∅ THEN ← SubOpt(∅, 1) END IF WHILE pphase1 not completely constructed DO pphase1 ← GetBest() ← SubOpt(pphase1, inext subproblem) END WHILE pphase2 ← GetBest() WHILE not stagnate DO ← ∅ FOR each subproblem i DO ← SubOpt(pphase2,i) END FOR ← Collab() pphase2 ← GetBest() END WHILE END WHILE 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Constructive cooperative coevolution」の詳細全文を読む スポンサード リンク
|